#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<float> costs = {33333.333, 2059.003, 5750.501, 8143.093, 18026.02, 19987.834, 10234.741, 8378.319, 948.933, 400.446, 3335.015, 1629.893, 384.841, 1146.454, 137.977, 132.672, 40.421, 29.208, 18.352, 42.342, 8.037, 19479.29};
float target = 33333.333; // 30fps

/**
 * 抽象为装箱问题：有n个箱子，每个箱子容量为target，问如何分配costs，使得使用的箱子数最少。
 * 可用NF近似解法解决。TODO: 看一下算法的课件求一下装箱问题近似解法的近似比。把必须分开的先放入不同的箱子中。
 */

// 自适应，确定每个Function的 instance_number 和 batch_size
void adjust(){
    
}

// 进行组合，装箱问题
void group(){

}

int main(){
    // 理论最优值
    float sum = 0.0;
    int count = 0;
    for(int i = 0; i < costs.size(); i++){
        sum += costs[i];
        count++;
    }
    int min_count = sum/target + 1;
    cout << "理论最优解：" << min_count << endl;
    // 装箱问题近似解法：首次适宜法（近似比2），最适宜法（近似比1.7），首次适宜降序法，最适宜降序法，随机适应算法。
    /**
     * @brief 最适宜法
     * 
     */
    vector<int> Boxes;       // 箱子目前使用容量
    vector<vector<int>> res; // 每个箱子的装入情况
    for(int i = 0; i < costs.size(); i++){
        // 判断当前箱子能否装入，以及装入第几号箱子合适
        float minRemain = target;
        float minIndex = -1;
        for(int j = 0; j < Boxes.size(); j++){
            if((target - Boxes[j]) > costs[i] && (target - Boxes[j] - costs[i]) < minRemain){
                minRemain = target - Boxes[j] - costs[i];
                minIndex = j;
            }
        }
        if(minIndex == -1){ // 开辟新箱子装入
            Boxes.push_back(costs[i]);
            vector<int> newBox = {i};
            res.push_back(newBox);
        }else{ // 装入minIndex号箱子
            Boxes[minIndex] += costs[i];
            res[minIndex].push_back(i);
        }
    }
    cout << "使用箱子数：" << Boxes.size() << endl;
    for(auto i : Boxes){
        cout << i << " ";
    }
    cout << endl;
    for(auto i : res){
        for(auto j : i){
            cout << j << " ";
        }
        cout << endl;
    }
}